#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//自己
//int fib(int n)
//{
//	if (n < 3)
//	{
//		return 1;
//	}
//	else
//	{
//		return (fib(n - 1) + fib(n - 2));
//	}
//
//}
////答案
//int fib(int n)
//{
//	if (n <= 2)
//		return 1;
//	else
//		return fib(n - 1) + fib(n - 2);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = fib(n);
//	printf("%d", ret);
//
//	return 0;
//}
//求第n个斐波那契数。（不考虑溢出）

//我们发现 fib 函数在调用的过程中很多计算其实在一直重复。
//int count = 0;//全局变量
//int fib(int n)
//{
//	if (n == 3)
//		count++;
//	if (n <= 2)
//		return 1;
//	else
//		return fib(n - 1) + fib(n - 2);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = fib(n);
//	printf("%d", ret);
//
//	return 0;
//}//40的时候已经上亿了，50甚至很久没有出来
//不管是求阶乘还是斐波那契数列，此时非递归方式反而更好一些
//循环求阶乘
//循环(迭代)
//int fac(int n)
//{
//	int r = 1;
//	int i = 0;
//	for (i = 1; i <= n; i++)
//	{
//		r = r * i;
//	}
//	return r;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = fac(n);
//	printf("%d", ret);
//
//	return 0;
//}

//循环求斐波那契数列
//int Fib(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	//5 4 3
//	while (n >= 3)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//
//		n--;
//	}
//	return c;
//}
//
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fib(n);
//	printf("%d\n", ret);
//	//printf("count = %d\n", count);
//	return 0;
//}

//
//int Fib(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n >= 3)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//
//		n--;
//	}
//	return c;
//
//
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = Fib(n);
//	printf("%d\n", ret);
//	//printf("count = %d\n", count);
//	return 0;
////}
//许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
//2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
//3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开
//销
// 
////自己
//int Pow(int n, int k)
//{
//	if (k == 1)
//	{
//		return n;
//	}
//	else
//	{
//		return n * Pow(n, k - 1);
//	}
//}
//答案
//int Pow(int n, int k)
//{
//	if (k == 0)
//		return 1;
//	else if (k >= 1)
//	{
//		return n * Pow(n, k - 1);
//	}
//}
//int main()
//{
//	int n = 0;
//	int k = 0;
//	scanf("%d %d", &n, &k);
//	int ret = Pow(n, k);
//	printf("%d", ret);
//
//	return 0;
//}
//编写一个函数实现n的k次方，使用递归实现。
// 自己
//int DigitSum(int n)
//{
//	if (n < 10)
//	{
//		return n;
//	}
//	else
//	{
//		return (DigitSum(n / 10) + (n % 10));
//	}
//}
//答案
//int DigitSum(int n)//1729
//{
//	if (n > 9)
//		return DigitSum(n / 10) + n % 10;
//	else
//		return n;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int ret = DigitSum(n);
//	printf("%d", ret);
//	return 0;
//}
//计算一个数的每位之和（递归实现）
//作业内容
//写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//例如，调用DigitSum(1729)，则应该返回1 + 7 + 2 + 9，它的和是19
//输入：1729，输出：19
//递归方式：
//对于字符串“abcdefg”，递归实现的大概原理：
//1. 交换a和g，
//2. 以递归的方式逆置源字符串的剩余部分，剩余部分可以看成一个有效的字符串，再以类似的方式逆置
//* /
//void reverse_string(char* arr)
//{
//	int len = strlen(arr);
//	char tmp = *arr;
//	*arr = *(arr + len - 1);
//
//	*(arr + len - 1) = '\0';
//
//	if (strlen(arr + 1) >= 2)
//	{
//		reverse_string(arr + 1);
//
//	}
//	*(arr + len - 1) = tmp;
//}
//int main()
//{
//	char arr[] = "abcdef";
//	reverse_string(arr);
//	printf("%s", arr);
//	return 0;
//}
////字符串逆序（递归实现）
////作业内容
////编写一个函数 reverse_string(char* string)（递归实现）
////实现：将参数字符串中的字符反向排列，不是逆序打印。
////要求：不能使用C函数库中的字符串操作函数。
////比如 :char arr[] = "abcdef";
////逆序之后数组的内容变成：fedcba